#include <stdlib.h>
#include <stdio.h>

struct Iterator {
    int *begin;
    int *end;
};

struct Record {
    int val;
    int *cur;
    int *end;
};

int left_child( int i ) { return i*2+1; }
int right_child( int i ) { return i*2+2; } 
void swap( Record *a, Record *b ) {
    Record t = *a;
    *a = *b;
    *b = t;
}
void sift_down( Record *begin, int cur, Record *end ) {
    int last = end-begin;
    while( cur < last ) {
	const int left = left_child( cur );
	const int right = right_child( cur );
	int next = cur;
	if ( cur < right && (begin+right)->val < (begin+next)->val ) {
	    next = right;
	}
	if ( cur < left && (begin+left)->val < (begin+next)->val ) {
	    next = left;
	}
	if ( next == cur ) break;
	swap( begin+cur, begin+next );
	cur = next;
    }
}

void heapify( Record *begin, Record *end ) {
    int count = end - begin;
    while ( count >= 0 ) {
	sift_down( begin, count, end );
	count--;
    }
}

void print_merge( Iterator *begin,
		  Iterator *end ) {

    Record queues[end-begin];
    int size = 0;
    for ( Iterator *i = begin; i < end; i++ ) {
	if ( i->begin == i->end ) { continue; }
	Record *dst = queues+size;
	dst->val = *(i->begin);
	dst->cur = i->begin+1;
	dst->end = i->end;
	size++;
    }

    heapify( queues, queues+size );

    while ( size ) {
	printf("%d ", queues[0].val );
	if ( queues[0].cur == queues[0].end ) {
	    queues[0] = queues[size-1];
	    size--;
	} else {
	    queues[0].val = *(queues[0].cur);
	    queues[0].cur++;
	}
	sift_down( queues, 0, queues+size );
    }
    printf( "\n");
}

int main( int argc, char*argv[] ) {
    const int queues = 2;
    const int length = 10;
    int array[queues][length] = { {1,2,3,4,5,6,7,8,9,10},
				  {1,2,3,4,5,6,7,8,9,10} };
    Iterator its[queues];
    for ( int i = 0; i < queues; i++ ) {
	/* printf( "%d\n", &array[i][0] ); */
	its[i].begin = &array[i][0];
	its[i].end = &array[i][length];
    }
    print_merge( its, its+queues );
    return 0;
}
